package com.zdp.leetcodeMiddle;

/*
* 题目描述：
* 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：
输入：nums = [1]
输出：[1]
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 下一个排列_31 {
    public static void main(String[] args) {
        下一个排列_31 demo = new 下一个排列_31();
        int[] d = new int[]{
                1,2,3
        };
        demo.nextPermutation(d);
        for(int i : d){
            System.out.println(i);
        }
    }

    /*
    * 解题思路：重点在于 要找的是下一个更大的排列
    * 这也就意味着 我们所组成的新的排列，所增加的字典序要最小
    *  如何增加字典序？ ----> 在左边的较小的数与在右边的比他大的数交换，字典序就会增加
    *  如何增加最小的字典序？
    *  左边的那个较小的数 要最靠近右边  右边的那个较大数 数值应该最靠近左边的那个数
    * 两者交换后， 将较小数的那个位置后面的数组进行升序排列，保证字典序增加最小
    * */
    public void nextPermutation(int[] nums) {
        int n = nums.length-1;
        // 找到一个最靠右的升序对
        // 记录i的位置
        int i = n-1;
        for(;i>=0;i--){
            if(nums[i]<nums[i+1]){
                break;
            }
        }
        // 这样 i+1 ~ n 都是降序对
        // 找到尽可能小的 那个大于nums[i]的那个数
        if(i>=0){
            int j = n;
            for(;j>i;j--){
                if(nums[j]>nums[i])
                    break;
            }
            // 交换 i 和 j
            swap(nums,i,j);
        }
        // 然后将 i位置后面的数组倒置，因为i+1~n是降序的，所以导致就变成升序
        // 这些步骤都是为了保证，这次调整让数组的字典序以最小的代价增加--->下一个更大的排列
        reverse(nums,i+1,n);

    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void reverse(int[] nums,int start,int end){
        while(start<end){
            swap(nums,start++,end--);
        }
    }
}
